package leetcode_900;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *RaceCar_818 一辆汽车可以加速可以掉头 问最短多少步到达目的地
 *describe:用广度优先遍历 AC 29%
 *2018年10月29日 上午9:27:50
 */
public class RaceCar_818 {
	 class CarInfo{
	        int pos, speed;
	        public CarInfo(int p, int s) {
	            pos = p;
	            speed = s;
	        }
	    }
	    public int racecar(int target) {
	        Set<String> visited = new HashSet<>();
	        String begin = 0 + "/" + 1;
	        visited.add(begin);
	        Queue<CarInfo> queue = new LinkedList<>();
	        queue.add(new CarInfo(0,1));
	        int level = 0;
	        while (!queue.isEmpty()) {
	            int size = queue.size();
	            for(int i = 0; i < size; i++) {
	                CarInfo cur = queue.poll();
	                if (cur.pos == target) return level;
	                String s1 = (cur.pos + cur.speed) + "/" + (cur.speed * 2);
	                String s2 = cur.pos + "/" + (cur.speed > 0 ? -1 : 1);
	                if (Math.abs(cur.pos + cur.speed - target) < target && !visited.contains(s1)) {
	                    visited.add(s1);
	                    queue.add(new CarInfo(cur.pos + cur.speed, cur.speed * 2));
	                }
	                if (Math.abs(cur.pos - target) < target && !visited.contains(s2)) {
	                    visited.add(s2);
	                    queue.add(new CarInfo(cur.pos, cur.speed > 0 ? -1 : 1));
	                }
	            }
	            
	            level++;
	        }
	        return -1;
	    }

}
